#include <iostream>
#include <vector>
#include <string>
using namespace std;

bool findPathCore(const vector<vector<char>> &input,
                  const int &row,
                  const int &col,
                  const int &total_row,
                  const int &total_col,
                  const string &str,
                  const int &str_idx,
                  vector<vector<bool>> &has_visited) {
  if (str_idx == str.size()) {
    return true;
  }
  bool ret = false;
  if (row >= 0 && row < total_row &&
      col >= 0 && col < total_col &&
      input[row][col] == str[str_idx] &&
      has_visited[row][col] == false) {
    has_visited[row][col] = true;
    ret = findPathCore(input, row + 1, col, total_row, total_col, str, str_idx + 1, has_visited) ||
          findPathCore(input, row - 1, col, total_row, total_col, str, str_idx + 1, has_visited) ||
          findPathCore(input, row, col + 1, total_row, total_col, str, str_idx + 1, has_visited) ||
          findPathCore(input, row, col - 1, total_row, total_col, str, str_idx + 1, has_visited);
    if (!ret) {
      has_visited[row][col] = false;
    }
  }
  return ret;
}

bool findPath(const vector<vector<char>> &input, const string &str) {
  int total_row = input.size();
  int total_col = input[0].size();
  vector<vector<bool>> has_visited;
  has_visited.resize(total_row);
  for (auto i = 0; i < total_row; ++i) {
    // has_visited[i].resize(total_col);
    has_visited[i].assign(total_col, 0);
  }

  for (int i = 0; i < total_row; ++i) {
    for (int j = 0; j < total_col; ++j) {
      if (findPathCore(input, i, j, total_row, total_col, str, 0, has_visited)) {
        return true;
      }
    }
  }
  return false;
}

int main() {
  vector<vector<char>> input = {{'a', 'b', 't', 'g'},
                                {'c', 'f', 'c', 's'},
                                {'j', 'd', 'e', 'h'}};
  cout << "findPath: " << findPath(input, "bfce") << " expect result: 1" << endl;
  cout << "findPath: " << findPath(input, "bfcea") << " expect result: 0" << endl;
  return 0;
}
